home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / russell / gc32.lha / malloc.c < prev    next >
C/C++ Source or Header  |  1993-07-20  |  10KB  |  390 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1993 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to copy this garbage collector for any purpose,
  9.  * provided the above notices are retained on all copies.
  10.  */
  11.  
  12. #include <stdio.h>
  13. #include "gc_private.h"
  14.  
  15. extern void GC_clear_stack();    /* in misc.c */
  16.  
  17. # ifdef ALL_INTERIOR_POINTERS
  18. #   define SMALL_OBJ(bytes) ((bytes) < WORDS_TO_BYTES(MAXOBJSZ))
  19. #   define ADD_SLOP(bytes) ((bytes)+1)
  20. # else
  21. #   define SMALL_OBJ(bytes) ((bytes) <= WORDS_TO_BYTES(MAXOBJSZ))
  22. #   define ADD_SLOP(bytes) (bytes)
  23. # endif
  24.  
  25.  
  26. /* allocate lb bytes for an object of kind.    */
  27. /* Should not be used to directly to allocate    */
  28. /* objects such as STUBBORN objects that    */
  29. /* require special handling on allocation.    */
  30. /* First a version that assumes we already    */
  31. /* hold lock:                    */
  32. ptr_t GC_generic_malloc_inner(lb, k)
  33. register word lb;
  34. register int k;
  35. {
  36. register word lw;
  37. register ptr_t op;
  38. register ptr_t *opp;
  39.  
  40.     if( SMALL_OBJ(lb) ) {
  41. #       ifdef MERGE_SIZES
  42.       lw = GC_size_map[lb];
  43. #    else
  44.       lw = ROUNDED_UP_WORDS(lb);
  45.       if (lw == 0) lw = 1;
  46. #       endif
  47.     opp = &(GC_obj_kinds[k].ok_freelist[lw]);
  48.         if( (op = *opp) == 0 ) {
  49.             if (!GC_is_initialized) {
  50.                 GC_init_inner();
  51.                 return(GC_generic_malloc_inner(lb, k));
  52.             }
  53.             GC_clear_stack();
  54.         op = GC_allocobj(lw, k);
  55.         if (op == 0) goto out;
  56.         }
  57.         /* Here everything is in a consistent state.    */
  58.         /* We assume the following assignment is    */
  59.         /* atomic.  If we get aborted            */
  60.         /* after the assignment, we lose an object,    */
  61.         /* but that's benign.                */
  62.         /* Volatile declarations may need to be added    */
  63.         /* to prevent the compiler from breaking things.*/
  64.         *opp = obj_link(op);
  65.         obj_link(op) = 0;
  66.     } else {
  67.     register struct hblk * h;
  68.     register word n_blocks = divHBLKSZ(lb + HDR_BYTES + HBLKSIZE-1);
  69.     
  70.     if (!GC_is_initialized) GC_init_inner();
  71.     /* Do our share of marking work */
  72.           if(GC_incremental && !GC_dont_gc) GC_collect_a_little((int)n_blocks);
  73.     lw = ROUNDED_UP_WORDS(lb);
  74.     while ((h = GC_allochblk(lw, k)) == 0
  75.         && GC_collect_or_expand(n_blocks));
  76.     if (h == 0) {
  77.         op = 0;
  78.     } else {
  79.         op = (ptr_t) (h -> hb_body);
  80.         GC_words_wasted += BYTES_TO_WORDS(n_blocks * HBLKSIZE) - lw;
  81.     }
  82.     }
  83.     GC_words_allocd += lw;
  84.     
  85. out:
  86.     return((ptr_t)op);
  87. }
  88.  
  89. ptr_t GC_generic_malloc(lb, k)
  90. register word lb;
  91. register int k;
  92. {
  93.     ptr_t result;
  94.     DCL_LOCK_STATE;
  95.  
  96.     DISABLE_SIGNALS();
  97.     LOCK();
  98.     result = GC_generic_malloc_inner(lb, k);
  99.     UNLOCK();
  100.     ENABLE_SIGNALS();
  101.     return(result);
  102. }   
  103.  
  104.  
  105. /* Analogous to the above, but assumes a small object size, and     */
  106. /* bypasses MERGE_SIZES mechanism.  Used by gc_inline.h.        */
  107. ptr_t GC_generic_malloc_words_small(lw, k)
  108. register word lw;
  109. register int k;
  110. {
  111. register ptr_t op;
  112. register ptr_t *opp;
  113. DCL_LOCK_STATE;
  114.  
  115.     DISABLE_SIGNALS();
  116.     LOCK();
  117.     opp = &(GC_obj_kinds[k].ok_freelist[lw]);
  118.     if( (op = *opp) == 0 ) {
  119.         if (!GC_is_initialized) {
  120.             GC_init_inner();
  121.         }
  122.         GC_clear_stack();
  123.     op = GC_allocobj(lw, k);
  124.     if (op == 0) goto out;
  125.     }
  126.     *opp = obj_link(op);
  127.     obj_link(op) = 0;
  128.     GC_words_allocd += lw;
  129.     
  130. out:
  131.     UNLOCK();
  132.     ENABLE_SIGNALS();
  133.     return((ptr_t)op);
  134. }
  135.  
  136. /* Allocate lb bytes of atomic (pointerfree) data */
  137. # ifdef __STDC__
  138.     extern_ptr_t GC_malloc_atomic(size_t lb)
  139. # else
  140.     extern_ptr_t GC_malloc_atomic(lb)
  141.     size_t lb;
  142. # endif
  143. {
  144. register ptr_t op;
  145. register ptr_t * opp;
  146. register word lw;
  147. DCL_LOCK_STATE;
  148.  
  149.     if( SMALL_OBJ(lb) ) {
  150. #       ifdef MERGE_SIZES
  151.       lw = GC_size_map[lb];
  152. #    else
  153.       lw = ROUNDED_UP_WORDS(lb);
  154. #       endif
  155.     opp = &(GC_aobjfreelist[lw]);
  156.     FASTLOCK();
  157.         if( !FASTLOCK_SUCCEEDED() || (op = *opp) == 0 ) {
  158.             FASTUNLOCK();
  159.             return(GC_generic_malloc((word)lb, PTRFREE));
  160.         }
  161.         /* See above comment on signals.    */
  162.         *opp = obj_link(op);
  163.         GC_words_allocd += lw;
  164.         FASTUNLOCK();
  165.         return((extern_ptr_t) op);
  166.    } else {
  167.        return((extern_ptr_t)
  168.                GC_generic_malloc((word)lb, PTRFREE));
  169.    }
  170. }
  171.  
  172. /* Allocate lb bytes of composite (pointerful) data */
  173. # ifdef __STDC__
  174.     extern_ptr_t GC_malloc(size_t lb)
  175. # else
  176.     extern_ptr_t GC_malloc(lb)
  177.     size_t lb;
  178. # endif
  179. {
  180. register ptr_t op;
  181. register ptr_t *opp;
  182. register word lw;
  183. DCL_LOCK_STATE;
  184.  
  185.     if( SMALL_OBJ(lb) ) {
  186. #       ifdef MERGE_SIZES
  187.       lw = GC_size_map[lb];
  188. #    else
  189.       lw = ROUNDED_UP_WORDS(lb);
  190. #       endif
  191.     opp = &(GC_objfreelist[lw]);
  192.     FASTLOCK();
  193.         if( !FASTLOCK_SUCCEEDED() || (op = *opp) == 0 ) {
  194.             FASTUNLOCK();
  195.             return(GC_generic_malloc((word)lb, NORMAL));
  196.         }
  197.         /* See above comment on signals.    */
  198.         *opp = obj_link(op);
  199.         obj_link(op) = 0;
  200.         GC_words_allocd += lw;
  201.         FASTUNLOCK();
  202.         return((extern_ptr_t) op);
  203.    } else {
  204.        return((extern_ptr_t)
  205.               GC_generic_malloc((word)lb, NORMAL));
  206.    }
  207. }
  208.  
  209. /* Allocate lb bytes of pointerful, traced, but not collectable data */
  210. # ifdef __STDC__
  211.     extern_ptr_t GC_malloc_uncollectable(size_t lb)
  212. # else
  213.     extern_ptr_t GC_malloc_uncollectable(lb)
  214.     size_t lb;
  215. # endif
  216. {
  217. register ptr_t op;
  218. register ptr_t *opp;
  219. register word lw;
  220. DCL_LOCK_STATE;
  221.  
  222.     if( SMALL_OBJ(lb) ) {
  223. #       ifdef MERGE_SIZES
  224.       lw = GC_size_map[lb];
  225. #    else
  226.       lw = ROUNDED_UP_WORDS(lb);
  227. #       endif
  228.     opp = &(GC_uobjfreelist[lw]);
  229.     FASTLOCK();
  230.         if( FASTLOCK_SUCCEEDED() && (op = *opp) != 0 ) {
  231.             /* See above comment on signals.    */
  232.             *opp = obj_link(op);
  233.             obj_link(op) = 0;
  234.             GC_words_allocd += lw;
  235.             GC_set_mark_bit(op);
  236.             GC_non_gc_bytes += WORDS_TO_BYTES(lw);
  237.             FASTUNLOCK();
  238.             return((extern_ptr_t) op);
  239.         }
  240.         FASTUNLOCK();
  241.         op = (ptr_t)GC_generic_malloc((word)lb, UNCOLLECTABLE);
  242.     } else {
  243.     op = (ptr_t)GC_generic_malloc((word)lb, UNCOLLECTABLE);
  244.     }
  245.     /* We don't need the lock here, since we have an undisguised     */
  246.     /* pointer.  We do need to hold the lock while we adjust        */
  247.     /* mark bits.                            */
  248.     {
  249.     register struct hblk * h;
  250.     
  251.     h = HBLKPTR(op);
  252.     lw = HDR(h) -> hb_sz;
  253.     
  254.     DISABLE_SIGNALS();
  255.     LOCK();
  256.     GC_set_mark_bit(op);
  257.     GC_non_gc_bytes += WORDS_TO_BYTES(lw);
  258.     UNLOCK();
  259.     ENABLE_SIGNALS();
  260.     return((extern_ptr_t) op);
  261.     }
  262. }
  263.  
  264. extern_ptr_t GC_generic_or_special_malloc(lb,knd)
  265. word lb;
  266. int knd;
  267. {
  268.     switch(knd) {
  269. #     ifdef STUBBORN_ALLOC
  270.     case STUBBORN:
  271.         return(GC_malloc_stubborn((size_t)lb));
  272. #     endif
  273.     case UNCOLLECTABLE:
  274.         return(GC_malloc_uncollectable((size_t)lb));
  275.     default:
  276.         return(GC_generic_malloc(lb,knd));
  277.     }
  278. }
  279.  
  280.  
  281. /* Change the size of the block pointed to by p to contain at least   */
  282. /* lb bytes.  The object may be (and quite likely will be) moved.     */
  283. /* The kind (e.g. atomic) is the same as that of the old.          */
  284. /* Shrinking of large blocks is not implemented well.                 */
  285. # ifdef __STDC__
  286.     extern_ptr_t GC_realloc(extern_ptr_t p, size_t lb)
  287. # else
  288.     extern_ptr_t GC_realloc(p,lb)
  289.     extern_ptr_t p;
  290.     size_t lb;
  291. # endif
  292. {
  293. register struct hblk * h;
  294. register hdr * hhdr;
  295. register signed_word sz;     /* Current size in bytes    */
  296. register word orig_sz;     /* Original sz in bytes    */
  297. int obj_kind;
  298.  
  299.     if (p == 0) return(GC_malloc(lb));    /* Required by ANSI */
  300.     h = HBLKPTR(p);
  301.     hhdr = HDR(h);
  302.     sz = hhdr -> hb_sz;
  303.     obj_kind = hhdr -> hb_obj_kind;
  304.     sz = WORDS_TO_BYTES(sz);
  305.     orig_sz = sz;
  306.  
  307.     if (sz > WORDS_TO_BYTES(MAXOBJSZ)) {
  308.     /* Round it up to the next whole heap block */
  309.       
  310.       sz = (sz+HDR_BYTES+HBLKSIZE-1)
  311.         & (~HBLKMASK);
  312.       sz -= HDR_BYTES;
  313.       hhdr -> hb_sz = BYTES_TO_WORDS(sz);
  314.       if (obj_kind == UNCOLLECTABLE) GC_non_gc_bytes += (sz - orig_sz);
  315.       /* Extra area is already cleared by allochblk. */
  316.     }
  317.     if (ADD_SLOP(lb) <= sz) {
  318.     if (lb >= (sz >> 1)) {
  319. #        ifdef STUBBORN_ALLOC
  320.             if (obj_kind == STUBBORN) GC_change_stubborn(p);
  321. #        endif
  322.         if (orig_sz > lb) {
  323.           /* Clear unneeded part of object to avoid bogus pointer */
  324.           /* tracing.                          */
  325.           /* Safe for stubborn objects.                  */
  326.             bzero(((char *)p) + lb, (int)(orig_sz - lb));
  327.         }
  328.         return(p);
  329.     } else {
  330.         /* shrink */
  331.           extern_ptr_t result =
  332.                   GC_generic_or_special_malloc((word)lb, obj_kind);
  333.  
  334.           if (result == 0) return(0);
  335.               /* Could also return original object.  But this     */
  336.               /* gives the client warning of imminent disaster.    */
  337.           bcopy(p, result, (int)lb);
  338.           GC_free(p);
  339.           return(result);
  340.     }
  341.     } else {
  342.     /* grow */
  343.       extern_ptr_t result =
  344.           GC_generic_or_special_malloc((word)lb, obj_kind);
  345.  
  346.       if (result == 0) return(0);
  347.       bcopy(p, result, (int)sz);
  348.       GC_free(p);
  349.       return(result);
  350.     }
  351. }
  352.  
  353. /* Explicitly deallocate an object p.                */
  354. # ifdef __STDC__
  355.     void GC_free(extern_ptr_t p)
  356. # else
  357.     void GC_free(p)
  358.     extern_ptr_t p;
  359. # endif
  360. {
  361.     register struct hblk *h;
  362.     register hdr *hhdr;
  363.     register signed_word sz;
  364.     register ptr_t * flh;
  365.     register int knd;
  366.     register struct obj_kind * ok;
  367.  
  368.     if (p == 0) return;
  369.         /* Required by ANSI.  It's not my fault ...    */
  370.     h = HBLKPTR(p);
  371.     hhdr = HDR(h);
  372.     knd = hhdr -> hb_obj_kind;
  373.     sz = hhdr -> hb_sz;
  374.     GC_mem_freed += sz;
  375.     ok = &GC_obj_kinds[knd];
  376.     if (knd == UNCOLLECTABLE) GC_non_gc_bytes -= sz;
  377.   
  378.     if (sz > MAXOBJSZ) {
  379.     GC_freehblk(h);
  380.     } else {
  381.         ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
  382.     if (ok -> ok_init) {
  383.         bzero((char *)((word *)p + 1), (int)(WORDS_TO_BYTES(sz-1)));
  384.     }
  385.     flh = &(ok -> ok_freelist[sz]);
  386.     obj_link(p) = *flh;
  387.     *flh = (ptr_t)p;
  388.     }
  389. }
  390.